import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Test59 {
    public static List<Integer> maxInWindows(List<Integer> data, int size){
        List<Integer> windowMax = new ArrayList<>();

        // 条件检查
        if (data == null || size < 1 || data.size() < 1) {
            return windowMax;
        }
        //存储索引值
        Deque<Integer> deq = new LinkedList<>();
        //窗口还没有被填满时，找到最大值的索引
        for (int i = 0; i< size && i < data.size();i++){
            // 如果索引对应的值比之前存储的索引值对应的值大或者相等，就删除之前存储的值
            while (!deq.isEmpty() && data.get(i) >= data.get(deq.getLast()))
                deq.removeLast();
            //否则将索引添加到队列的末尾，或者队列已经清空，将最大值放入队列
            deq.addLast(i);
        }
        for (int i = size;i < data.size();i++){
            //第一个窗口的最大值保存
            windowMax.add(data.get(deq.getFirst()));
            // 如果索引对应的值比之前存储的索引值对应的值大或者相等，就删除之前存储的值
            while (!deq.isEmpty() && data.get(i) >= data.get(deq.getLast()))
                deq.removeLast();
            //删除已经画出窗口的数据对应的下标
            if(!deq.isEmpty() &&deq.getFirst() <= (i-size)) deq.removeFirst();
            //将可能的最大值放入队尾
            deq.add(i);
        }
        windowMax.add(data.get(deq.getFirst()));//最后一个串口的最大值
        return windowMax;
    }
    private static List<Integer> arrayToCollection(int[] array) {
        List<Integer> result = new LinkedList<>();
        if (array != null) {
            for (int i : array) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // expected {7};
        List<Integer> data1 = arrayToCollection(new int[]{1, 3, -1, -3, 5, 3, 6, 7});
        System.out.println(data1 + "," + maxInWindows(data1, 10));

        // expected {3, 3, 5, 5, 6, 7};
        List<Integer> data2 = arrayToCollection(new int[]{1, 3, -1, -3, 5, 3, 6, 7});
        System.out.println(data2 + "," + maxInWindows(data2, 3));
    }

}
